#include <iostream>

using namespace std;

template <class T>
class Node
{
public:
    T data;
    Node *next;
};

template <class T>
class LinkList : public Node<T>
{

public:
    Node<T> *head;
    int length;

    LinkList<T>();
    LinkList<T>(const LinkList<T> &linklist);
    void creatList(const int &n);
    void rearInsert(const T &data);
    bool Insert(const T &data, int position);
    int Find(const T &data);
    bool Delete(const int &position);
    void Reserve();

    LinkList<T> *Merge(const LinkList<T> &linklist);

    ~LinkList<T>();
};

template <class T>
LinkList<T>::LinkList()
{
    this->head = new Node<T>();
    this->head->next = nullptr;
    this->length = 0;
}

template <class T>
LinkList<T>::LinkList(const LinkList<T> &linklist)
{
}

/**
 * @brief 创建大小为N的链表
 *
 * @tparam T ElemType
 * @param n 链表大小
 */
template <class T>
void LinkList<T>::creatList(const int &n)
{
    if (length == 0)
    {
        for (int i = 0; i < n; i++)
        {
            cout << "输入第" << i + 1 << "个元素:" << endl;
            T inData;
            cin >> inData;
            this->rearInsert(inData);
            this->length++;
        }
    }
    else
    {
        cout << "Error: LinkList is not empty" << endl;
    }
}

/**
 * @brief 尾插节点
 *
 * @tparam T ElemType
 * @param data 节点数据
 */
template <class T>
void LinkList<T>::rearInsert(const T &data)
{
    Node<T> *p = new Node<T>();
    p->data = data;
    p->next = nullptr;
    Node<T> *cur = head;
    while (cur->next != nullptr)
    {
        cur = cur->next;
    }
    cur->next = p;

    this->length++;
}

/**
 * @brief 在position位置之后插入一个新的节点
 *
 * @tparam T ElemType
 * @param data 节点数据
 * @param position 插入位置
 * @return true 插入成功
 * @return false 插入失败
 */
template <class T>
bool LinkList<T>::Insert(const T &data, int position)
{
    if (position > this->length)
    {
        cout << "Error: Out of Length";
        return false;
    }
    else
    {
        Node<T> *newNode = new Node<T>(), *cur = this->head;
        newNode->data = data;
        newNode->next = nullptr;
        for (int i = 0; i < position; i++)
        {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        this->length++;
        return true;
    }
}

/**
 * @brief 查找数据为data的节点位置position
 *
 * @tparam T ElemType
 * @param data 匹配数据
 * @return int 位置
 */
template <class T>
int LinkList<T>::Find(const T &data)
{
    Node<T> *cur = this->head->next;
    int position = 1;
    if (this->head->next == nullptr)
    {
        return 0;
    }
    while (cur != nullptr && cur->data != data)
    {
        position++;
        cur = cur->next;
    }
    if (cur == nullptr)
    {
        return 0;
    }
    return position;
}

/**
 * @brief 删除位于position的节点
 *
 * @tparam T ElemType
 * @param position 删除位置
 * @return true 删除成功
 * @return false 删除失败
 */
template <class T>
bool LinkList<T>::Delete(const int &position)
{
    if (position > length)
    {
        return false;
    }
    Node<T> *cur = this->head->next, *pre = this->head;
    for (int i = 1; i < position; i++)
    {
        cur = cur->next;
        pre = pre->next;
    }
    pre->next = cur->next;
    delete cur;
    this->length--;
    return true;
}

template <class T>
ostream &operator<<(ostream &out, const LinkList<T> &linklist)
{
    if (linklist.head != nullptr)
    {
        out << "head->";
        Node<T> *p = linklist.head->next;
        while (p != nullptr)
        {
            out << p->data << "->";
            p = p->next;
        }
        out << "NULL" << endl;
    }
    return out;
}

template <class T>
void LinkList<T>::Reserve()
{
    Node<T> *t = nullptr;
    Node<T> *cur = this->head->next;
    Node<T> *temp;
    while (cur != nullptr)
    {
        temp = t;
        t = cur;
        cur = cur->next;
        t->next = temp;
        // cout << t->data << " ";
    }
    this->head->next = t;
}

/**
 * @brief 题2算法实现
 *
 * @tparam T
 * @param linklist
 * @return LinkList<T>*
 */
template <class T>
LinkList<T> *LinkList<T>::Merge(const LinkList<T> &linklist)
{
    LinkList<T> *retList = new LinkList<T>();
    Node<T> *cur1 = this->head->next, *cur2 = linklist.head->next, *cur3 = retList->head;
    while (cur1 != nullptr && cur2 != nullptr)
    {
        if (cur1->data < cur2->data)
        {
            Node<T> *newNode = new Node<T>();
            newNode->data = cur1->data;
            newNode->next = nullptr;
            cur3->next = newNode;
            cur3 = cur3->next;
            cur1 = cur1->next;
        }
        else if (cur1->data > cur2->data)
        {
            Node<T> *newNode = new Node<T>();
            newNode->data = cur2->data;
            newNode->next = nullptr;
            cur3->next = newNode;
            cur3 = cur3->next;
            cur2 = cur2->next;
        }
        else
        {
            Node<T> *newNode = new Node<T>();
            newNode->data = cur2->data;
            newNode->next = nullptr;
            cur3->next = newNode;
            cur3 = cur3->next;
            cur2 = cur2->next;
            cur1 = cur1->next;
        }

        if (cur1 == nullptr)
        {
            cur1 = cur2;
        }

        while (cur1 != nullptr)
        {
            Node<T> *newNode = new Node<T>();
            newNode->data = cur1->data;
            newNode->next = nullptr;
            cur3->next = newNode;
            cur3 = cur3->next;
            cur1 = cur1->next;
        }
        cur3->next = nullptr;
    }
    return retList;
}

template <class T>
LinkList<T>::~LinkList()
{
    while (this->head != nullptr)
    {
        Node<T> *cur = this->head;
        this->head = cur->next;
        delete cur;
    }
    this->length = 0;
}